import java.util.Arrays;

import java.util.*;

public class Test {
    public static int maxProfit(int[] prices) {
        int[] nums=new int[10];
        int i=0;
        int left=0;
        int right=prices.length-1;
        while(left<prices.length-1){
            if(left==right){
                left++;
                right=prices.length-1;
            }
            if(prices[left]>prices[right]){
                left++;
                right=prices.length-1;
            }else{
                nums[i]=prices[right]-prices[left];
                if(nums.length-1==i){
                    nums=grow(nums);
                }
                i++;
                right--;
            }

        }
        Arrays.sort(nums);
        return nums[nums.length-1];
    }

    public static  int[] grow(int[] arr){
        return Arrays.copyOf(arr,arr.length*2);
    }
    public static void main(String[] args) {
        int[] arr=new int[]{2,1,4};
        int a=maxProfit(arr);
        System.out.println(a);
    }
    public static List<Integer> getRow(int rowIndex) {
        List<List<Integer>> lim=new LinkedList<>();
        List<Integer> lin=new LinkedList<>();
        for (int i = 0; i < rowIndex+1; i++) {
            List<Integer> list=new LinkedList<>();

            for (int j = 0; j <=i ; j++) {
                if(j==0){
                    list.add(1);
                }
                else if(j==i){
                    list.add(1);
                } else{
                    list.add(lin.get(j)+lin.get(j-1));
                }

            }
            lim.add(list);
            lin=lim.get(i);

        }

        return lim.get(rowIndex);
    }
    public static List<List<Integer>> generate(int numRows) {

        List<List<Integer>> lim=new LinkedList<>();
        List<Integer> lin=new LinkedList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> list=new LinkedList<>();

            for (int j = 0; j <=i ; j++) {
                if(j==0){
                    list.add(1);
                }
                else if(j==i){
                    list.add(1);
                } else{
                    list.add(lin.get(j)+lin.get(j-1));
                }

            }
            lim.add(list);
            lin=lim.get(i);

        }
        return lim;

    }

    public static void main3(String[] args) {
        List<Integer> list=getRow(3);
        System.out.println(list);
    }
    public static void main2(String[] args) {
        List<List<Integer>> list=  generate(5);
        System.out.println(list);
        System.out.println("111");
    }
    public static void main1(String[] args) {
        int[] arr=new int[]{1,2,5,8,9};
        int tmp=1;
        int k=arr.length-1;
        for (int i = arr.length; i >0 ; i--) {

            if(arr[k]+tmp==10){
                if(k==0){
                    arr=new int[arr.length+1];
                    for(int j=arr.length-2;j>=0;j--){
                        arr[j+1]=arr[j];
                    }
                    arr[k]=1;
                    break;
                }
                arr[k]=0;
                tmp=1;
            }else{
                if(tmp==1){
                    arr[k]=arr[k]+tmp;
                    tmp=0;
                }
            }
            k--;
        }
        System.out.println(Arrays.toString(arr));
    }
}
